#pragma once
#include <iostream>
#include<vector>
#include<fstream>
#include<string>
#include<iomanip>
#include<sstream>
#include <algorithm>
using namespace std;


// 计算next数组
inline vector<int> NextArray(const string& pattern) {
    int n = pattern.length();
    vector<int> next(n);
    next[0] = 0;
    int cn = 0;
    for (int i = 1; i < n; ++i) {
        if (pattern[i] == pattern[cn]) {
            next[i] = cn++;
        }
        else {
            if (cn != 0) {
                cn = next[cn - 1];
                --i;
            }
            else {
                next[i] = 0;
            }
        }
    }
    return next;
}

// KMP匹配算法
inline bool KMP(string text, string pattern) {
    vector<int> next = NextArray(pattern);
    int i = 0, j = 0; // text和pattern的索引
    while (i < text.length()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == pattern.length()) {
            return 1;     //匹配成功
        }
        else if (i < text.length() && pattern[j] != text[i]) {
            // 不匹配，移动模式串的索引
            if (j != 0) {
                j = next[j - 1];
            }
            else {
                i = i + 1;
            }
        }
    }
    //匹配失败
    return 0;
}

//注意：要弄为内联函数以防链接器错误